Module# 13: Searching Techniques Lecture#49: Programs for Searching
// Example 49.1: Programming for linear search
algorithm
/* This program
search an array of elements. The program works well whether the array elements
are in sorted order or not. */
class LinearSearch<T extends Comparable<T>> {
public int search(T[] arr, T x, int len) {
for(int i = 0; i < len; i++) {
if(arr[i] == x)
return i;
}
return -1;
}
}
class LinearSearchDemo {
public static void main(String args[]) {
LinearSearch<Integer> l = new LinearSearch<Integer>();
Integer
arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
Integer
x = 10;
// Integer result =
search(arr, x, n);
if(l.search(arr, x, n) == -1)
System.out.print("Element is not
present in array");
else
System.out.print("Element is
present at index " + l.search(arr, x, n));
}
}
// Example 49.2:
Programming for Binary Search algorithm
/* This program
implements the Binary Search Algorithm over an array of sorted numbers. */
class BinarySearch<T extends Comparable<T>> {
int binarySearch(T[] arr, int l, int r, T x) {
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then it
can only be present in left subarray
if (arr[mid].compareTo(x)==1)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present in
right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
in array
return -1;
}
}
class BinarySearchDemo{
// Driver method to test above
public static void main(String args[])
{
BinarySearch<Integer> ob = new BinarySearch<Integer>();
Integer arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
Integer x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not
present");
else
System.out.println("Element found
at index " + result);
}
}
// Example 49.3:
Programming for Interpolation search algorithm
/* Interpolation
Search with Generic type. */
class InterpolationSearch<T extends Number & Comparable<T>>{
//Declaring an array, which should store any
type T of data
T a[ ]; // Define that the
array a[ ] can store any type of data
InterpolationSearch(T x[]) { // Define a constructor
a = x;
}
T getData(int i) {
// To return the element stored in the i-th place in the array
return a[i];
}
void printData() {
// A generic method to print the elements in array a
for(int i = 0; i < a.length; i ++)
System.out.print(getData(i) + "
"); // Print the i-th
element in a
System.out.println(); // Print a new line
}
T sub(T x, T y) {
if (x == null || y == null)
return null;
if (x instanceof Double)
return (T) new Double(x.doubleValue() - y.doubleValue());
if (x instanceof Integer)
return (T) new Integer(x.intValue() - y.intValue());
if (x instanceof Short)
return (T)new Integer(x.shortValue() - y.shortValue());
if (x instanceof Byte)
return (T)new Integer(x.byteValue() - y.byteValue());
if (x instanceof Float)
return (T)new Float(x.floatValue() - y.floatValue());
if (x instanceof Long)
return (T)new Long(x.longValue() - y.longValue());
else
throw new IllegalArgumentException("Type " + x.getClass() + " is not
supported”);
}
int interpolationSearch(T k) {
int l=0,u=a.length-1;
while(l<=u && k.compareTo(a[l])>=0 && k.compareTo(a[u])<=0) {
if (l == u) {
if (a[l].compareTo(k)==0) return l;
return -1;
}
/int loc=((k-a[l])/(a[u]-a[l]))*(u-l)+l;
int n=sub(k,a[l]).intValue();
int d=sub(a[u],a[l]).intValue();
int loc=(n/d)*(u-l)+l;
int result=k.compareTo(a[loc]);
if(result==-1) u=--loc;
else if (result==0) return loc;
else l=++loc;
}
return -1;
} // End of the method interpolationSerach
} // End of the class InterpolationSerach
public class
InterpolationSearchDemo {
public static void main(String[] args){
// Searching with integer data
Integer i[ ] = {10, 20, 30, 40, 50};
// Store the data into generic array
InterpolationSearch<Integer> arrayInt = new InterpolationSearch<Integer>(i);
// Printing the data….
arrayInt.printData();
int searchInt=20;
int pos=arrayInt.interpolationSearch(searchInt);
if(pos==-1)
System.out.println(searchInt+" not found in
the array");
else
System.out.println(searchInt+" found at
position "+pos);
System.out.println();
// Searching with
float values
Double d[ ] = {10.5, 20.5, 30.5, 40.5, 50.5};
// Store the data into generic array
InterpolationSearch<Double> arrayDouble = new InterpolationSearch<Double>(d);
// Printing the data….
arrayDouble.printData();
Double searchDouble=30.5;
pos=arrayDouble.interpolationSearch(searchDouble);
if(pos==-1)
System.out.println(searchDouble+" not found in
the array");
else
System.out.println(searchDouble+" found at
position "+pos);
System.out.println();
// Searching with
short values
Short s[ ] = {10, 20, 30, 40, 50};
// Store the data into generic array
InterpolationSearch<Short> arrayShort = new InterpolationSearch<Short>(s);
// Printing the data….
arrayShort.printData();
Short searchShort=40;
pos=arrayShort.interpolationSearch(searchShort);
if(pos==-1)
System.out.println(searchShort+" not found in
the array");
else
System.out.println(searchShort+" found at
position "+pos);
System.out.println();
// Searching with byte values
Byte b[ ] = {10, 20, 30, 40, 50};
// Store the data into generic array
InterpolationSearch<Byte> arrayByte = new InterpolationSearch<Byte>(b);
// Printing the data….
arrayByte.printData();
Byte searchByte=50;
pos=arrayByte.interpolationSearch(searchByte);
if(pos==-1) System.out.println(searchByte+" not found in the array");
else System.out.println(searchByte+" found at position "+pos);
System.out.println();
} // End of the main method
} // End of the class
InerpolationSearchDemo
// Example 49.4:
Binary search on an array
// This program illustrates the use of Binary
Search method.
import java.util.Arrays;
public class
BinarySerachArraysDemo {
public static void main(String[] args){
// Get the Array
int intArr[] = { 10, 20, 15, 22, 35};
Arrays.sort(intArr);
int intKey = 22;
System.out.println(intKey
+ " found at index
= "
+ Arrays.binarySearch(intArr, intKey));
}
}
// Example 49.5:
Binary search on a sub-list of an array
/* This program
illustrates the use of Binary Search method within a sub list. */
import java.util.Arrays;
public class
ArraysBinarySerachSubListDemo {
public static void main(String[] args){
int intArr[] = { 10, 20, 15, 22, 35}; // An int array as input
Arrays.sort(intArr); // Sort the array
int intKey = 22;
System.out.println ( intKey + " found at index = "
+ Arrays.binarySearch(intArr, 1, 3, intKey));
}
}